package leetcode.tree;

/**
 * @author 榆关
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同
 */
public class VerifySquenceOfBST {
    public static void main(String[] args) {
        VerifySquenceOfBST bst = new VerifySquenceOfBST();
        int[] s = {7,4,6,5};
        System.out.println(bst.VerifySquenceOfBST(s));
    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        //思路
        //二叉树的后序遍历的最后一位是根节点，前面由左子树和右子树构成
        //左子树都比根节点小，右子树都比跟节点大
        boolean result = true;
        int length = sequence.length;
        //根节点
        int root = sequence[length-1];
        int beginIndex = -1;
        //从头开始找，第一个大于根节点的数
        //如果没有，则说明都为左子树
        for(int i=0;i<length-1;i++){
            if(sequence[i]>root){
                beginIndex = i;
                break;
            }
        }
        //开始比较beginIndex右边的序列与根节点的大小，只要有一个小于root，就返回false
        if(beginIndex > -1){
            for(int i=beginIndex;i<length-1;i++){
                if(sequence[i] < root){
                    result = false;
                    break;
                }
            }
        }
        return result;
    }
}
